package ACM_Brush;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class Solution239 {
    public static void main(String[] args) {
        int[] array = new int[] { 1, 3, -1, -3, 5, 3, 6, 7 };
        int k = 3;
        int[] result = new Solution_239().maxSlidingWindow(array, k);
        for (int i = 0; i < result.length; i++) {
            System.out.println(result[i]);
        }
    }
}

class Solution_239 {
    public int[] maxSlidingWindow(int[] array, int k) {
        List<Integer> list = new ArrayList<>();
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return b[0] - a[0];
            }
        });

        for (int i = 0; i < k; i++)
            pq.add(new int[] { array[i], i });

        list.add(pq.peek()[0]);

        for (int i = k; i < array.length; i++) {
            pq.add(new int[] { array[i], i });
            while(pq.peek()[1] <= i - k)
                pq.poll();
            list.add(pq.peek()[0]);
        }

        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}
